package _2022.hot100._102_二叉树的层序遍历;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * @author： YHSimon
 * @date： 2022-04-24 16:25
 */
public class Solution {

    // 递归实现
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans=new ArrayList<>();
        if(root!=null){
            dfs(ans,root,0);
        }
        return ans;
    }

    private void dfs(List<List<Integer>> ans, TreeNode node, int level) {
        if(ans.size()-1<level){
            ans.add(new ArrayList<>());
        }
        ans.get(level).add(node.val);
        if(node.left!=null){
            dfs(ans, node, level+1);
        }
        if(node.right!=null){
            dfs(ans, node,level+1);
        }
    }

    // 迭代实现 广度优先遍历

    public List<List<Integer>> levelOrder2(TreeNode root){
        List<List<Integer>> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> tmp=new ArrayList<>();
            int curLevelSize=queue.size();
            for(int i=1;i<=curLevelSize;++i){
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            res.add(tmp);
        }
        return res;
    }
}
